//数字 3797 有一个有趣的性质：它自己是一个素数，同时我们可以从左至右逐步截断这个数
//        字，得到 3797，797，97 和 7，它们也都是素数。同样，我们也可以从右至左逐步截断这个
//        数字，得到 3797，379，37 和 3 也都是素数。求仅有的十一个从左至右和从右至左都可以截
//        短的素数之和(注：2，3，5 和 7 不被认为是可截短素数)。
//        答案：748317

public class Week037 {
    static void run() {
        int N = 5000000;
        int[] primes = new int[N >> 1];
        int[] mv = new int[N];
        int tot = Week035.getPrime(primes, mv, N - 1);
        int ans = 0;
        for (int i = 4; i < tot; ++i) {
            boolean yes = true;
            String s = Integer.toString(primes[i]);
            int len = s.length();
            for (int j = 1, t; yes && j < len; ++j) {
                t = Integer.parseInt(s.substring(j));
                if (mv[t] != t) yes = false;//不是质数
            }
            for (int j = len - 1, t; yes && j > 0; --j) {
                t = Integer.parseInt(s.substring(0, j));
                if (mv[t] != t) yes = false;//不是质数
            }
            if (yes) ans += primes[i];
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
